package com.wdc.binarytree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Binary Search Tree 二叉搜索树
 */
public class BSTTree1 {

    BSTNode root; //根节点

    public BSTTree1() {
    }

    public BSTTree1(BSTNode root) {
        this.root = root;
    }

    /**
     * 获取
     * @return root
     */
    public BSTNode getRoot() {

        return root;
    }

    /**
     * 设置
     * @param root
     */
    public void setRoot(BSTNode root) {
        this.root = root;
    }

    public String toString() {
        return "BSTTree1{root = " + root + "}";
    }

    static class BSTNode {

        int key;
        Object value;
        BSTNode left;
        BSTNode right;

        public BSTNode(int key) {
            this.key = key;
        }

        public BSTNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }


    /**
     * 查找关键字对应的值
     *
     * @param key 关键字
     * @return 关键字对应的值
     */
    public Object get(int key) {
        return doGet(root,key);
    }

    //封装递归函数
    private Object doGet(BSTNode node, int key) {
        if (node == null){
            return null;
        }
        if (key < node.key) {
           return doGet(node.left, key);  // 向左找
        } else if (key > node.key) {
            return doGet(node.right, key);  //向右找
        } else {
            return node.value; //找到了
        }
    }

    //非递归代码效率更高
    public Object getNoUse(int key){
        BSTNode node = root;
        while( node != null ){
            if (key < node.key){
                node = node.left;
            } else if (key > node.key) {
                node = node.right;
            }else {
                return node.value;
            }
        }
        return null;
    }





    /**
     * 查找最大关键字对应值
     *
     * @return
     */
    public Object max() {

        if (root == null){
            return null;
        }
        BSTNode node  =root;
        while(node.right != null){
            node = node.right;
        }

        return node.value;
    }

    /**
     * 找任意结点的最大值
     * @param p
     * @return
     */
    private Object max(BSTNode p){
        if (p == null){
            return null;
        }
        BSTNode node  =p;
        while(node.right != null){
            node = node.right;
        }

        return node.value;
    }


    /**
     * 查找最小关键字对应值
     *
     * @return
     */
    public Object min() {
        BSTNode node = root;
        if (node == null){
            return null;
        }
        while (node.left != null){
            node = node.left;
        }

        return node.value;
    }

    private Object min(BSTNode p){
        BSTNode node = p;
        if (p == null){
            return null;
        }
        while (node.left != null){
            node = node.left;
        }

        return node.value;
    }

    //min 的递归版本实现
    public Object doMin(BSTNode node){
        if (node == null){
            return null;
        }
        if (node.left == null){
            return node.value;
        }
        return doMin(node.left);
    }

    /**
     * 查找关键字的前驱值
     *
     * @param key 关键字
     * @return 前驱值
     */
    public Object successor(int key) {

        BSTNode node = root;
        BSTNode ancestorFromLeft = null;
        //1、先找到这个key 所在的位置
        while (node != null) {
            if (node.key < key) {
                ancestorFromLeft = node;
                node = node.right;
            } else if (node.key > key) {

                node = node.left;
            }else{
                break; //说明找到了
            }

        }

        //2、判断 这个key 的值是否存在如果存在就分情况讨论
        if (node.value == null){
            return null;
        }

        //2.1、判断是否有左子树，

        //2.2 如果有左子树，则左子树中最大的就是它的前任
        if (node.left != null){
           return max(node.left);

        }
        //2.3、 如果没有则离他最近，自左而来的祖先就是前任

        return ancestorFromLeft != null ? ancestorFromLeft.value : null;



    }


    /**
     * 查找关键字的后继值
     *
     * @param key 关键字
     * @return 后继值
     */
    public Object predecessor(int key) {
        BSTNode ancestorFromRight = null;
        //1. 先找到key 的值
        BSTNode node = root;

        while (node != null) {
            if (key > node.key){
                node = node.right;
            }else if (key < node.key){
                ancestorFromRight = node;
                node = node.left;
            }else {
                break;
            }
        }
        //2. 判断是否存在，不存在则返回null
        if (node == null){
            return null;
        }
        //3. 如果该节点有右子树，则右子树中的最小值则是该节点的后继
        if (node.right != null){
            return min(node.right);
        }
        //3. 如果该节点没有右子树，则离它最近的从右而来的祖先则是它的后继


        return  ancestorFromRight != null ? ancestorFromRight.value : null;
    }

    /**
     * 根据关键字删除
     *
     * @param key 关键字
     * @return 被删除关键字对应的值
     */
    public Object delete(int key) {
        //1. 先找到该key 的节点值
        BSTNode node = root;
        BSTNode parent = root;
        while( node != null ){
            if (key < node.key){
                parent = node;
                node = node.left;
            } else if (key > node.key) {
                parent = node;
                node = node.right;
            }else {
               break;
            }
            if (node == null){
                return null;
            }

            //进行删除操作
            if (node.left == null ){
                 //删除节点没有左孩子，将右孩子托孤给 Parent
                shift(parent,node,node.right);
            } else if (node.right == null ) {
                //删除节点没有右孩子，将左孩子托孤给 parent
                shift(parent,node,node.left);
            } else {
                //被删除节点找后继
                BSTNode s = node.right;
                BSTNode sParent = node; //后继节点的父亲
                while (s.left != null){
                    sParent = s;
                    s = s.left;
                }
                //即后继节点即为 s
                if (sParent != node){ //不相等
                    //删除和后继不相邻，处理后继的后事
                    shift(sParent,s,s.right);
                    s.right =node.right;

                }
                //后继取代被删除的节点
                shift(parent,node,s);
                s.left = node.left;

            }


        }

        return null;
    }

    /**
     * 托孤方法
     * @param parent 被删除节点的父亲
     * @param deleted 被删除节点
     * @param child 被顶上去的节点
     */
    private void shift(BSTNode parent,BSTNode deleted,BSTNode child){

        //如果要删除根节点
        if (parent == null){
            root = child;
        }else if (deleted == parent.left){
            parent.left = child;
        }else {
            parent.right = child;
        }


    }


    /**
     * 存储关键字和对应值
     * @param key
     * @param value
     */
    public void put(int key, Object value){
        BSTNode node = root;
        BSTNode parent = null;
        while (node != null){
            parent = node;
            if (key < node.key){
                node = node.left;
            } else if (key > node.key ) {
                node = node.right;
            } else {
                // key已经有了，需要更新key 对应的值
                node.value = value;
                return;
            }
        }
        if (parent ==null){
            root = new BSTNode(key, value);
            return;
        }
        //没有 ，新增一个节点  与父节点判断 ，看是左孩子还是右孩子
        BSTNode added = new BSTNode(key, value);
        if (parent.key < key){
            parent.right = added;
        } else if (parent.key > key) {
            parent.left = added;
        }

    }

    /**
     * 找 < key 的所有 value
     * @param key
     * @return
     */
    public List<Object> less(int key){
        ArrayList<Object> result = new ArrayList<>();
        //遍历树，找比key 小的
        BSTNode curr = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (curr != null || !stack.isEmpty()){
            if (curr != null){
                //不为空就把树压栈
                stack.push(curr);
                curr = curr.left;
            } else {
                //左边压入了该弹栈
                BSTNode pop = stack.pop();
                //进行处理
                if (pop.key < key){
                    result.add(pop.value);
                }else {
                    break;
                }

                //遍历右子树
                curr =  pop.right;
            }
        }

        return result;
    }

    /**
     * 找 > key 的所有 value
     * 可以用反向中序遍历来优化
     * @param key
     * @return
     */
    public List<Object> greater(int key){
        ArrayList<Object> result = new ArrayList<>();

        //遍历树，找比key 大的
        BSTNode curr = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (curr != null || !stack.isEmpty()){
            if (curr != null){
                //不为空就把树压栈
                stack.push(curr);
                curr = curr.left;
            } else {
                //左边压入了该弹栈
                BSTNode pop = stack.pop();
                //进行处理
                if (pop.key > key){
                    result.add(pop.value);
                }
                //不能提前结束

                //遍历右子树
                curr =  pop.right;
            }
        }

        return result;
    }

    /**
     * 找 >= key1 且 <= key2 的所有值
     * @param key1
     * @return
     */
    public List<Object> between(int key1, int key2){
        ArrayList<Object> result = new ArrayList<>();

        //遍历树，找在key1,key2 中间的
        BSTNode curr = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (curr != null || !stack.isEmpty()){
            if (curr != null){
                //不为空就把树压栈
                stack.push(curr);
                curr = curr.left;
            } else {
                //左边压入了该弹栈
                BSTNode pop = stack.pop();
                //进行处理
                if (pop.key >= key1 && pop.key <= key2){
                    result.add(pop.value);
                } else if (pop.key > key2) {
                   break;
                }

                //遍历右子树
                curr =  pop.right;
            }
        }

        return result;
    }


}
